首先 844. Backspace String Compare (easy)
https://leetcode.com/problems/backspace-string-compare/

給一個字串s，s裡面有"#"，"#"是倒退鍵，會把前面的字刪除。
要輸出最終結果。

想法：

1. 建立stack存放英文字母
2. 讀取到"#"時pop stack裡的東西
3. 最後輸出stack裡的東西，結束

class Solution:
    # "#"即為Backspace，會把前面的字母刪去
    def backspaceCompare(self, s: str, t: str) -> bool:
        def cal(x):
            stack = []
            for i in x:
                if i != "#":
                    stack.append(i)
                else:
                    if stack:
                        stack.pop()
            return "".join(stack)
        
        return cal(s) == cal(t)

接下來是 394. Decode String (medium)
https://leetcode.com/problems/decode-string/

會給一個字串s，裡面含有四種元素："英文字母"、"數字"、"左中括弧"、"右中括弧"。範例如下：
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

想法如下：

1. 要分成四個部分討論：遇到左中括弧、遇到右中括弧、遇到數字、遇到文字
2. 建立三個空的東西分別儲存
   a. stack儲存完整的數字或文字
   b. num儲存數字
   c. now儲存文字
   3.遇到中左括弧，把完整的字跟數字丟到stack裡面
   4.遇到中右括弧，把stack裡的數字跟文字進行整理後放到now(最後會變成答案)

class Solution:
    def decodeString(self, s):
        stack = []
        num = ""
        now = ''
        for i in s:
            # print(stack)
            if i == '[':
                stack.append(num)
                stack.append(now)
                now = ''
                num = ""
            elif i == ']':#遇到右括弧就代表要開始收官了
                front = stack.pop()
                tempNum = stack.pop()
                now = front + int(tempNum)*now
            elif i.isdigit():
                num += i
            else:
                now += i
        return now

再來是 692. Top K Frequent Words (medium)
https://leetcode.com/problems/top-k-frequent-words

給一個文字串列 words，給一個整數k，要從words裡面找出前k個常出現的元素。

Example 1:
Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]

想法：

1. 計算每個單詞出現的頻率
2. 進行排序，首先用數字大小排，排好後用字典順序排
3. 結束

class Solution:
    #k代表是排名
    #也就是前k個常出現的
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        c = [(i,v) for i,v in Counter(words).items()]
        c.sort(key = lambda x:(-x[1],x[0]))
        ans = [c[i][0] for i in range(k)]
        # print(c)
        # print(ans)
        return ans

然後有看到有人用heap來寫，但個人覺得有點複雜所以放棄了。

以上為今天的練習，感謝大家的觀看